/**
 * 
 */
package array;

import java.util.List;
import java.util.PriorityQueue;
import java.util.LinkedList;
import java.util.ArrayList;

import utils.CreateUtils;
import utils.PrintUtils;

import datastructure.Pair;

/**
 * @author Michael
	// suppose each of the k arrays contains n elements
	// so there are kn elements in total
	// we do kn times of heapify, each heapify taking log(k)
	// so the total time complexity is O(knlog(k))
	// without heap it is gonna be O(kkn)?
 */
public class MergeKSortedArrays {

	public static List<Integer> merge(int[][] a) {
		assert (a != null && a.length > 0);
		
		for (int[] arr : a) {
			assert (arr != null);
		}
		
		PriorityQueue<Pair<Integer, Integer>> heap = new PriorityQueue<Pair<Integer, Integer>>();
		int[] positions = new int[a.length];
		List<Integer> list = new ArrayList<Integer>();
		
		
		for (int i = 0; i < a.length; i++) {
			if (a[i].length > 0) {
				heap.add(new Pair<Integer, Integer>(a[i][0], i));
				positions[i]++;
			}
		}
		
		while (!heap.isEmpty()) {
			Pair<Integer, Integer> pair = heap.poll();
			list.add(pair.first);
			int index = pair.second;
			if (positions[index] < a[index].length) {
				pair.first = a[index][positions[index]++];
				heap.add(pair);
			}
		}
		
		return list;
	}
	
	
	/**
	 * 
	 */
	public MergeKSortedArrays() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int k = 5;
		int[][] a = new int[k][];
		for (int i = 0; i < k; i++) {
			a[i] = CreateUtils.randSortedNonNegIntArray(10, 10);
			PrintUtils.printArray(a[i]);
		}
		PrintUtils.printList(merge(a));

	}

}
